206. Reverse Linked List

Reverse a singly linked list.

思路: 将head元素里的各个指针方向设为相反反向, 然后再让pre指向head最后一个指针就行

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        //通过改变指针指向
        while(cur != null ){
            ListNode nexttemp = cur.next;
            cur.next = pre;
            pre = cur; //更新pre指向cur
            cur = nexttemp; //更新cur
        }
        return pre;
    //为什么在这return cur/head 结果不一样:因为head指向第一个元素而cur指向最后一个
    }
}

再来个递归算法

递归版本稍微复杂一些,关键是向后退。假设列表的其余部分已经被颠倒了,现在如何扭转前面部分? 我们假设列表是:n 1 →...→n k-1 →n k →n k + 1 →...→n m →Ø 从节点n k + 1到n m的假设已经被反转,并且在节点n k处。 n 1 →...→n k-1 → n k →n k + 1 ←...←n m 我们希望n k + 1的下一个节点指向n k。 所以,n k .next.next = n k ; 要小心,n 1的下一个必须指向Ø。如果您忘记了这一点,您的链接列表就会有一个循环。

//C++
ListNode* reverseList(ListNode* head) {
    if (head == null || head->next == null) return head;
    ListNode* p = reverseList(head->next);
    head->next->next = head;
    head->next = null;
    return p;
}

//Java实现
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}